package exercise;
import java.util.Arrays;

/**
 * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 * 必须 原地 修改，只允许使用额外常数空间。
 */
public class exercise08 {
    public void nextPermutation(int[] nums) {

        int index = -1;
        int min = 0;
        for (int i = nums.length-1; i > 0; i--) {// 找到第一个升序的位置，替换成比他大1的
            if(nums[i] > nums[i-1]){
                index = i-1;
                min = nums[i-1];
                break;
            }
        }
        if(index == -1){// 没有升序，只有降序，直接排序返回
            Arrays.sort(nums);
            return;
        }
        int temp = nums[index+1] - min;
        int change = index+1;
        for (int i = index+2; i < nums.length; i++) {
            if((nums[i] > min) && (temp > nums[i] - min)){
                temp = nums[i] - min;
                change = i;
            }
        }
        temp = nums[index];
        nums[index] = nums[change];
        nums[change] = temp;
        // 升序排列
        Arrays.sort(nums,index+1,nums.length);
    }
    public static void main(String[] args) {
        exercise08 exercise08 = new exercise08();
        int[] nums = {1,3,3,1,3,3};
        exercise08.nextPermutation(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
    }
}
